/**
 * 
 */
package dp.passed;

/**
 * @author michaelyi
 *
 */
public class MaximumSubarray {

	/**
	Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

	For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
	the contiguous subarray [4,−1,2,1] has the largest sum = 6.
	 */
	public int maxSubArray(int[] A) {
		int minSum = 0;
		int maxSum = A[0];
		int accuSum = A[0];
		for (int i = 1; i < A.length; i++) {
			minSum = accuSum < minSum ? accuSum : minSum;
			accuSum += A[i];
			maxSum = accuSum - minSum > maxSum ? accuSum - minSum : maxSum;
		}

		return maxSum;
	}

	public int maxSubArrayLanb(int[] A) {
		if (A == null || A.length == 0) {
			return 0;
		}

		int max = A[0];
		int result = 0;
		int temp = 0;
		for (int i : A) {
			max = Math.max(max, i);
			temp = Math.max(0, temp + i);
			result = Math.max(result, temp);
		}

		if (max >= 0)
			return result;
		else
			return max;
	}

	public int maxSum(int[] a) {
		//check
		if (a == null || a.length == 0)
			return 0;

		int minSum = 0;
		int maxSum = a[0];
		int accuSum = a[0];
		for (int i = 1; i < a.length; i++) {
			if (accuSum < minSum)
				minSum = accuSum;
			accuSum += a[i];
			int temp = accuSum - minSum;
			if (temp > maxSum)
				maxSum = temp;

		}

		return maxSum;
	}

	/**
	http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
	*/
	//	public int maxSub2dArray(int[] A) {
	//
	//	}

	/**
	 * 
	 */
	public MaximumSubarray() {
		// TODO Auto-generated constructor stub
	}

	public int calcMaxSum1(int[] arr) {
		assert (arr != null);
		if (arr.length == 0) {
			return 0;
		}

		int maxSum = arr[0];
		for (int currCumulation = arr[0], minCumulation = 0, i = 1; i < arr.length; ++i) {
			minCumulation = currCumulation < minCumulation ? currCumulation
					: minCumulation;
			currCumulation += arr[i];
			maxSum = currCumulation - minCumulation > maxSum ? currCumulation
					- minCumulation : maxSum;
		}
		return maxSum;
	}

	/*
	public int[] calcMaxSumArray(int[] arr) {
		assert (arr != null);
		if (arr.length == 0)	{ return null; }
		
		int maxSum = arr[0];
		int start = 0;
		int end = 1;
		int 
		for (int currCumulation = arr[0], minCumulation = 0, i = 1;
				i < arr.length; ++i) {
			minCumulation = currCumulation < minCumulation ? currCumulation : minCumulation;
			currCumulation += arr[i];
			int diff = currCumulation - minCumulation;
			if (diff > maxSum) {
				maxSum = diff;
				start = 
			}
			maxSum = currCumulation - minCumulation > maxSum ? currCumulation - minCumulation : maxSum;
		}
		return maxSum;
	}
	*/
	public int calcMaxSum2(int[] arr) {
		assert (arr != null && arr.length > 0);

		int maxSum = arr[0];
		int minCumulation = 0;
		int curCumulation = arr[0];
		for (int i = 1; i < arr.length; ++i) {
			if (minCumulation > curCumulation) {
				minCumulation = curCumulation;
			}
			curCumulation = curCumulation + arr[i];
			int diff = curCumulation - minCumulation;
			if (diff > maxSum) {
				maxSum = diff;
			}
		}

		return maxSum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MaximumSubarray lsa = new MaximumSubarray();
		int[] arr = new int[] { -5 };
		System.out.printf("max sum (-5) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { 1, 5 };
		System.out.printf("max sum (6) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { -1, 5 };
		System.out.printf("max sum (5) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { 5, -1 };
		System.out.printf("max sum (5) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { -5, -6, -1, -2 };
		System.out.printf("max sum (-1) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { 2, 3, 7, 1 };
		System.out.printf("max sum (13) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { 0, 0, 0, 0 };
		System.out.printf("max sum (0) is %d\n", lsa.calcMaxSum1(arr));
		arr = new int[] { -1, 2, 3, -5, 4 };
		System.out.printf("max sum (5) is %d\n", lsa.calcMaxSum1(arr));

		// error case
		/*
		arr = new int[]{};
		System.out.printf("max sum (5) is %d", lsa.calcMaxSum(arr));
		arr = null;
		System.out.printf("max sum (5) is %d", lsa.calcMaxSum(arr));
		*/

	}

}
